1. Field of the Invention
This invention relates generally to multithreaded computer systems, and more specifically to a system and method for mitigating contention between concurrent threads of execution using transactional memory.
2. Description of the Related Art
Due to the complexity and energy concerns of modem processors, traditional approaches to boosting CPU performance have become difficult and ineffective. Instead of attempting to drive up clock speeds, computer architects are increasingly turning to multi-threading techniques such as symmetric multi-threading or multi-core architectures. In order to leverage these new architectures, software engineers must write applications that execute using multiple concurrent threads of execution. Unfortunately, correct multi-threaded programming is notoriously difficult using traditional language constructs.
Shared-memory systems allow multiple threads to access and operate on the same memory locations. To maintain consistency, threads must often execute a series of instructions as one atomic block, or critical section. In these cases, care must be taken to ensure that other threads do not observe memory values from a partial execution of such a block. Traditional constructs, such as mutual exclusion and locks may be used by a thread to ensure correctness by excluding all other threads from concurrent access to a critical section. For example, no thread may enter a critical section without holding the section's lock. While it does, all other threads wishing to execute the critical section must await the lock's release and acquire it before proceeding.
The pitfalls of these constructs are numerous and well known. They include dead-lock, race conditions, priority inversions, software complexity, and performance limitations. Locking entire critical sections is a heavy-handed approach to concurrency control.
Alternatively, it may be possible to increase parallelism by allowing multiple threads to execute a critical section at one time if the executions do not rely on overlapping memory locations. This may increase performance and mitigate many of the pitfalls normally associated with traditional locking mechanisms. However, such interleaved executions are not guaranteed to be correct.
Transactional memory is a mechanism that can be leveraged to enable concurrent and correct execution of a critical section by multiple threads. Transactional memory allows a thread to execute a block of instructions as a transaction, that is, either completely and atomically or not at all. The instructions are executed and then either “committed”, allowing the aggregate effect to be seen by all other threads, or “aborted”, allowing no effect to be seen. A transaction that has committed successfully may be said to have “succeeded”. Transactional lock-elision (TLE) is a technique that allows multiple threads to execute a critical section concurrently and transactionally without necessarily acquiring and holding a lock. It provides identical semantics to traditional mutual exclusion but allows threads to execute critical sections as transactions that can be aborted if a conflict occurs. Aborted transactions may be retried by the thread later.
Unfortunately, it is possible that repeated transactional aborts may lead to serious performance degradation. In the case of two or more concurrent transactions causing mutual aborts, the system could achieve even worse performance under a naïve or simplistic TLE policy than under traditional mutual exclusion.